home *** CD-ROM | disk | FTP | other *** search
/ Complete Linux / Complete Linux.iso / docs / apps / database / ingres04.lzh / source / iutil / insert_btree.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-09-18  |  15.4 KB  |  562 lines
  1. # include    <btree.h>
  2. # include    <ingres.h>
  3. # include    <batch.h>
  4. # include    <symbol.h>
  5. # include    <sccs.h>
  6.  
  7. SCCSID(@(#)insert_btree.c    8.1    12/31/84)
  8.  
  9. /*    INSERT_BTREE -- BTree insertion routine
  10. **
  11. **    Insert a tid into the BTree at the position corresponding to its lid.
  12. **    Split the leaf if necessary and adjust all values up the tree.
  13. **
  14. **    Parameters :
  15. **        tree - BTree filename (I)
  16. **        lid - given lid (I)
  17. **        tid - tid to be inserted into BTree leaf (I)
  18. **        tidpos - location where tid was inserted (O)
  19. **
  20. **    Returns :
  21. **        -1      lid position does not exist
  22. **        0    successful insertion
  23. */
  24.  
  25. insert_btree(tree, rootpage, lid, tid, tidpos, create)
  26.  
  27. char *tree;
  28. long rootpage;
  29. long lid;
  30. long *tid;
  31. register TID *tidpos;
  32. char create;
  33. {
  34.     register int        i, j, start;
  35.     struct locator        block, p;
  36.     struct BTreeNode    newblock, temp, newroot;
  37.     short            rblock, tline;
  38.     long            newpage, tpage;
  39.     long            get_tid(), new_page();
  40.     int            save;
  41.     char            replbatch[MAXNAME + 4];
  42.     FILE             *fp;
  43.     TID            oldtid, newtid;
  44.     long            count, page, childpage;
  45.     extern char        *Fileset;
  46.     extern DESC        Btreesec;
  47.  
  48. #    ifdef xATR1
  49.     if (tTf(24,0))
  50.         printf("inserting lid %ld into btree at rootpage %d", lid, rootpage);
  51. #    endif
  52.  
  53.     /* find location of desired lid in B-Tree */
  54.     if (get_tid(rootpage, lid, &block) < -1)
  55.         return(-1);
  56.  
  57.     if (newroot.depth = create)
  58.     {
  59.         if (save = block.offset)
  60.             newroot.prevtree = block.page.node.leafnode.tid_pos[block.page.node.leafnode.tid_loc[save -1]];
  61.         else
  62.         {
  63.             if (!block.page.prevtree)
  64.                 newroot.prevtree = 0;
  65.             else
  66.             {
  67.                 get_node(block.page.prevtree, &temp);
  68.                 newroot.prevtree = temp.node.leafnode.tid_pos[temp.node.leafnode.tid_loc[temp.nelmts - 1]];
  69.             }
  70.         }
  71.         if  (save <= block.page.nelmts - 1 && block.page.nelmts)
  72.             newroot.nexttree = block.page.node.leafnode.tid_pos[block.page.node.leafnode.tid_loc[save]];
  73.         else
  74.         {
  75.             if (!block.page.nexttree)
  76.                 newroot.nexttree = 0;
  77.             else
  78.             {
  79.                 get_node(block.page.nexttree, &temp);
  80.                 newroot.nexttree = temp.node.leafnode.tid_pos[temp.node.leafnode.tid_loc[0]];
  81.             }
  82.         }
  83.         *tid = new_page(tree);
  84.         if (block.pageno == RT)
  85.             get_node(RT, &block.page);
  86.         if (newroot.prevtree)
  87.         {
  88.             get_node(newroot.prevtree, &temp);
  89.             temp.nexttree = *tid;
  90.             write_node(newroot.prevtree, &temp);
  91.         }
  92.         if (newroot.nexttree)
  93.         {
  94.             get_node(newroot.nexttree, &temp);
  95.             temp.prevtree = *tid;
  96.             write_node(newroot.nexttree, &temp);
  97.         }
  98.         stuff_page(&newroot.prttree, &block.pageno);
  99.         newroot.nodetype = 'L';
  100.         newroot.nelmts = 0;
  101.         newroot.parent = 0;
  102.         newroot.node.leafnode.prevleaf = 0;
  103.         newroot.node.leafnode.nextleaf = 0;
  104.         for (i = 0; i < MAXLEAVES; ++i)
  105.             newroot.node.leafnode.tid_loc[i] = newroot.node.leafnode.back_ptr[i] = i;
  106.     }
  107.  
  108.     if (block.page.nelmts != MAXLEAVES)
  109.     /* insert tid into its proper position in leaf */
  110.     {
  111.         save = block.page.node.leafnode.tid_loc[block.page.nelmts];
  112.         /* move other tids down to make room for new tid */
  113.         for (i = block.page.nelmts - 1; i >= block.offset; --i)
  114.         {
  115.             block.page.node.leafnode.tid_loc[i + 1] =
  116.                 block.page.node.leafnode.tid_loc[i];
  117.             block.page.node.leafnode.back_ptr[block.page.node.leafnode.tid_loc[i]] = i + 1;
  118.         }
  119.         block.page.node.leafnode.tid_loc[block.offset] = save;
  120.         block.page.node.leafnode.tid_pos[save] = *tid;
  121.         block.page.node.leafnode.back_ptr[save] = block.offset;
  122.         ++block.page.nelmts;
  123.         write_node(block.pageno, &block.page);
  124.         if (create)
  125.             newroot.prttree.line_id = save;
  126.  
  127.         /* trace up B-Tree, incrementing key values */
  128.         tracepath(rootpage, &block, 1);
  129.  
  130.         tpage = block.pageno;
  131.         tline = save;
  132.     }
  133.  
  134.     else
  135.     /* leaf is full, must be split */
  136.     {
  137.         /* determine where to split leaf */
  138.         start = MAXLEAVES / 2;
  139.         rblock = 0;
  140.  
  141.         if (block.offset > start)
  142.         /* new tid will be inserted in the new leaf */
  143.         {        
  144.             ++start;
  145.             rblock = 1;
  146.         }
  147.  
  148.         /* readjust all values in the old leaf and assign them for
  149.         ** the new leaf */
  150.  
  151.         block.page.nelmts = start;    /* assume new tid will be
  152.                         ** inserted into new leaf */
  153.         newpage = new_page(tree);
  154.         newblock.nodetype = 'L';
  155.         for (i = 0; i < MAXLEAVES; ++i)
  156.             newblock.node.leafnode.tid_loc[i] = newblock.node.leafnode.back_ptr[i] = i;
  157.         newblock.nelmts = MAXLEAVES + 1 - start;
  158.         newblock.parent = block.page.parent;
  159.         newblock.depth = 0;
  160.  
  161.         if (newblock.node.leafnode.nextleaf = block.page.node.leafnode.nextleaf)
  162.         {
  163.             get_node(newblock.node.leafnode.nextleaf, &temp);
  164.             temp.node.leafnode.prevleaf = newpage;
  165.             write_node(newblock.node.leafnode.nextleaf, &temp);
  166.         }
  167.         block.page.node.leafnode.nextleaf = newpage;
  168.         newblock.node.leafnode.prevleaf = block.pageno;
  169.  
  170.         /* create file for storing tids that must be replaced in btree
  171.         ** secondary relation
  172.         */
  173.         if (!bequal("_SYS", tree, 4) && !create)
  174.         {
  175.             concat(REPL_IN, Fileset, replbatch);
  176.             if ((fp = fopen(replbatch, "w")) == NULL)
  177.                 syserr("can't open batch file in insert_btree");
  178.             count = 0;
  179.             stuff_page(&oldtid, &block.pageno);
  180.             stuff_page(&newtid, &newpage);
  181.         }
  182.  
  183.         /* copy the right half of the old leaf onto the new leaf */
  184.         for (i = 0, j = start; j < MAXLEAVES || rblock == 1; ++i)
  185.         {
  186.             if (j == block.offset && rblock == 1)
  187.             /* current position in new leaf corresponds to position
  188.             ** of new tid */
  189.             {
  190.                 newblock.node.leafnode.tid_pos[newblock.node.leafnode.tid_loc[i]] = *tid;
  191.                 tline = newblock.node.leafnode.tid_loc[i];
  192.                 /* indicate that tid has been inserted */
  193.                 rblock = -1;
  194.             }
  195.             else
  196.             {
  197.                 childpage = newblock.node.leafnode.tid_pos[newblock.node.leafnode.tid_loc[i]] =
  198.                     block.page.node.leafnode.tid_pos[block.page.node.leafnode.tid_loc[j]];
  199.                 if (create)
  200.                 {
  201.                     get_node(childpage, &temp);
  202.                     stuff_page(&temp.prttree, &newpage);
  203.                     temp.prttree.line_id = newblock.node.leafnode.tid_loc[i];
  204.                     write_node(childpage, &temp);
  205.                 }
  206.                 if (!bequal("_SYS", tree, 4) && !create)
  207.                 {
  208.                     oldtid.line_id = block.page.node.leafnode.tid_loc[j];
  209.                     newtid.line_id = newblock.node.leafnode.tid_loc[i];
  210.                     if (fwrite(&oldtid, 1, LIDSIZE, fp) != LIDSIZE)
  211.                         syserr("write error in insert_btree");
  212.                     if (fwrite(&newtid, 1, LIDSIZE, fp) != LIDSIZE)
  213.                         syserr("write error in insert_btree");
  214.                     ++count;
  215.                 }
  216.                 ++j;
  217.             }
  218.         }
  219.         if (!bequal("_SYS", tree, 4) && !create)
  220.         {
  221.             fclose(fp);
  222.             repl_btree(replbatch, count);
  223.         }
  224.  
  225.         if (!rblock)
  226.         /* new tid belongs in old leaf, insert it into its proper 
  227.         ** position */
  228.         {
  229.             save = block.page.node.leafnode.tid_loc[block.page.nelmts];
  230.             for (i = block.page.nelmts - 1; i >= block.offset; --i)
  231.             {
  232.                 block.page.node.leafnode.tid_loc[i + 1] =
  233.                     block.page.node.leafnode.tid_loc[i];
  234.                 block.page.node.leafnode.back_ptr[block.page.node.leafnode.tid_loc[i]] = i + 1;
  235.             }
  236.             block.page.node.leafnode.tid_loc[block.offset] = save;
  237.             block.page.node.leafnode.tid_pos[save] = *tid;
  238.             block.page.node.leafnode.back_ptr[save] = block.offset;
  239.             tline = save;
  240.             /* readjust element counts to reflect that tid has been
  241.             ** placed in the old leaf */
  242.             ++block.page.nelmts;
  243.             --newblock.nelmts;
  244.         }
  245.  
  246.         if (block.pageno == rootpage)
  247.         {
  248.             /* split leaf was the root, a new level to the B-Tree
  249.             ** must be added */
  250.             rootsplit(tree, rootpage, &block, newpage, block.page.nelmts, newblock.nelmts);
  251.             newblock.parent = rootpage;
  252.             write_node(block.pageno, &block.page);
  253.             newblock.node.leafnode.prevleaf = block.pageno;
  254.             write_node(newpage, &newblock);
  255.  
  256.             if (create)
  257.             {
  258.                 for (i = 0; i < block.page.nelmts; ++ i)
  259.                 {
  260.                     get_node(block.page.node.leafnode.tid_pos[block.page.node.leafnode.tid_loc[i]], &temp);
  261.                     stuff_page(&temp.prttree, &block.pageno);
  262.                     write_node(block.page.node.leafnode.tid_pos[block.page.node.leafnode.tid_loc[i]], &temp);
  263.                 }
  264.             }
  265.             /* btree page has changed */
  266.             if (!bequal("_SYS", tree, 4) && !create)
  267.             {
  268.                 concat(REPL_IN, Fileset, replbatch);
  269.                 if ((fp = fopen(replbatch, "w")) == NULL)
  270.                     syserr("can't open batch file in insert_btree");
  271.                 count = 0;
  272.                 page = 0l;
  273.                 stuff_page(&oldtid, &page);
  274.                 stuff_page(&newtid, &block.pageno);
  275.                 for (i = 0; i < block.page.nelmts; ++i)
  276.                 {
  277.                     if (rblock || block.page.node.leafnode.tid_loc[i] != tline)
  278.                     {
  279.                         oldtid.line_id = newtid.line_id = block.page.node.leafnode.tid_loc[i];
  280.                         if (fwrite(&oldtid, 1, LIDSIZE, fp) != LIDSIZE)
  281.                             syserr("write error in insert_btree");
  282.                         if (fwrite(&newtid, 1, LIDSIZE, fp) != LIDSIZE)
  283.                             syserr("write error in insert_btree");
  284.                         ++count;
  285.                     }
  286.                 }
  287.                 fclose(fp);
  288.                 repl_btree(replbatch, count);
  289.             }
  290.         }
  291.         else
  292.         /* insert the pointer and key associated with new leaf into the
  293.         ** parent of the old leaf */
  294.         {
  295.             write_node(block.pageno, &block.page);
  296.             write_node(newpage, &newblock);
  297.             p.pageno = block.page.parent;
  298.             parentkey(block.pageno, &p);
  299.             p.page.node.intnode.key[p.offset] = block.page.nelmts;
  300.             insert_key(tree, rootpage, newpage, newblock.nelmts, &p);
  301.         }
  302.         tpage = (rblock) ? newpage : block.pageno;
  303.     }
  304.     stuff_page(tidpos, &tpage);
  305.     tidpos->line_id = tline;
  306.  
  307.     if (create)
  308.         write_node(*tid, &newroot);
  309.  
  310. }
  311.  
  312. /*
  313. **    Takes a pair of tids from a file and sequentially replaces the
  314. **    old tid with the new tid in the secondary btree relation
  315. */
  316.  
  317. repl_btree(replbatch, count)
  318. register char *replbatch;
  319. long count;
  320. {
  321.     register int    i, j;
  322.     TID        uptid;
  323.     DESC        d;
  324.     char        tids[2 * LIDSIZE], key[2 * LIDSIZE], newkey[2 * LIDSIZE];
  325.     extern DESC    Btreesec;
  326.     extern char    *ztack();
  327.  
  328.     if (count > 0)
  329.     {
  330.         /* set up descriptor for sort */
  331.         d.reloff[1] = 0;
  332.         d.reloff[2] = LIDSIZE;
  333.         d.relfrmt[1] = d.relfrmt[2] = INT;
  334.         d.relfrml[1] = d.relfrml[2] = LIDSIZE;
  335.         d.relgiven[1] = 1;
  336.         d.relgiven[2] = 2;
  337.         d.reldum.relspec = M_ORDER;
  338.         d.reldum.relatts = 2;
  339.         d.reldum.relwid = 2 * LIDSIZE;
  340.         sortfile(replbatch, &d, FALSE);
  341.         if ((Repl_outfp = fopen(ztack(REPL_OUT, Fileset), "r")) == NULL)
  342.             syserr("can't open replace file after sort in insertbtreee\n");
  343.         clearkeys(&Btreesec);
  344.         for (i = 0; i < count; ++i)
  345.         {
  346.             if (fread(tids, 1, 2 * LIDSIZE, Repl_outfp) != 2 * LIDSIZE)
  347.                 syserr("read error in insert_btree");
  348.             setkey(&Btreesec, key, tids, 2);
  349.             if (getequal(&Btreesec, key, newkey, &uptid))
  350.             {
  351.                 printup(&Btreesec, key);
  352.                 syserr("getequal error in insert_btree");
  353.             }
  354.             /* place new tid in place */
  355.             setkey(&Btreesec, newkey, tids + LIDSIZE, 2);
  356.             if (j = replace(&Btreesec, &uptid, newkey, TRUE))
  357.                 if (j == 1)
  358.                     continue;
  359.                 else
  360.                     syserr("bad replace in insert_btree");
  361.         }
  362.         fclose(Repl_outfp);
  363.         unlink(replbatch);
  364.         unlink(ztack(REPL_OUT, Fileset));
  365.     }
  366. }
  367.  
  368. /*    Insert a key/ptr pair into a node, splitting nodes if necessary and
  369. **    adjusting values up the tree.
  370. **
  371. **    Parameters :
  372. **        tree - BTree filename (I)
  373. **        p - page number of newly formed node (I)
  374. **        k - key value of newly formed node (I)
  375. **        pkey - information about the node whose ptr/key pair is to
  376. **               be inserted (I, O)
  377. */
  378.  
  379. insert_key(tree, rootpage, p, k, pkey)
  380.  
  381. char *tree;
  382. long rootpage;
  383. long p, k;
  384. register struct locator *pkey;
  385. {
  386.     register int        i, j, start;
  387.     struct BTreeNode    newblock, temp;
  388.     long            newpage, oldkey, newkey;
  389.     struct locator        prt;
  390.     short            rblock;
  391.     long             new_page();
  392.  
  393.     if (pkey->page.nelmts != MAXPTRS)
  394.     /* insert pointer/key pair into proper position in node by moving
  395.     ** other pairs down node */
  396.     {
  397.         for (i = pkey->page.nelmts - 1; i >= pkey->offset + 1; --i)
  398.         {
  399.             pkey->page.node.intnode.ptr[i + 1] =
  400.                 pkey->page.node.intnode.ptr[i];
  401.             pkey->page.node.intnode.key[i + 1] =
  402.                 pkey->page.node.intnode.key[i];
  403.         }
  404.         ++pkey->page.nelmts;
  405.         pkey->page.node.intnode.ptr[pkey->offset + 1] = p;
  406.         pkey->page.node.intnode.key[pkey->offset + 1] = k;
  407.  
  408.         write_node(pkey->pageno, &pkey->page);
  409.  
  410.         /* trace up B-Tree incrementing keys */ 
  411.         tracepath(rootpage, pkey, 1);
  412.     }
  413.  
  414.     else
  415.     /* node is full, must be split */
  416.     {
  417.         /* determine where split will be made */
  418.         start = MAXPTRS / 2;
  419.         rblock = 0;
  420.  
  421.         if (pkey->offset + 1 > start)
  422.         /* ptr/key pair will be inserted in new node */
  423.         {
  424.             ++start;
  425.             rblock = 1;
  426.         }
  427.  
  428.         /* readjust old node values and create new node values */
  429.         pkey->page.nelmts = start;
  430.         newpage = new_page(tree);
  431.         newblock.nodetype = 'I';
  432.         newblock.nelmts = MAXPTRS + 1 - start;
  433.         newblock.parent = pkey->page.parent;
  434.         newblock.depth = 0;
  435.  
  436.         /* copy right side of old node into new node */
  437.  
  438.         for (i = 0, j = start; j < MAXPTRS || rblock == 1; ++i)
  439.         {
  440.             if (j == pkey->offset + 1 && rblock == 1)
  441.             /* node position corresponds to that of new ptr/key pair */
  442.             {
  443.                 newblock.node.intnode.ptr[i] = p;
  444.                 newblock.node.intnode.key[i] = k;
  445.                 /* make sure children of newblock have proper
  446.                 ** parent */
  447.                 get_node(p, &temp);
  448.                 temp.parent = newpage;
  449.                 write_node(p, &temp);
  450.  
  451.                 rblock = -1;
  452.             }
  453.             else
  454.             {
  455.                 newblock.node.intnode.ptr[i] =
  456.                     pkey->page.node.intnode.ptr[j];
  457.                 newblock.node.intnode.key[i] =
  458.                     pkey->page.node.intnode.key[j];
  459.                 /* make sure children of newblock have proper
  460.                 ** parent */
  461.                 get_node(newblock.node.intnode.ptr[i], &temp);
  462.                 temp.parent = newpage;
  463.                 write_node(newblock.node.intnode.ptr[i], &temp);
  464.                 ++j;
  465.             }
  466.         }
  467.  
  468.         if (!rblock)
  469.         /* insert new ptr/key pair into proper position in old node */
  470.         {
  471.             for (i = pkey->page.nelmts - 1; i >= pkey->offset + 1; --i)
  472.             {
  473.                 pkey->page.node.intnode.ptr[i + 1] =
  474.                     pkey->page.node.intnode.ptr[i];
  475.                 pkey->page.node.intnode.key[i + 1] =
  476.                     pkey->page.node.intnode.key[i];
  477.             }
  478.             pkey->page.node.intnode.ptr[pkey->offset + 1] = p;
  479.             pkey->page.node.intnode.key[pkey->offset + 1] = k;
  480.             ++pkey->page.nelmts;
  481.             --newblock.nelmts;
  482.         }
  483.  
  484.         /* calculate the key values of the old and new nodes */
  485.         oldkey = 0;
  486.         for (i = 0; i < pkey->page.nelmts; ++i)
  487.             oldkey += pkey->page.node.intnode.key[i];
  488.         newkey = 0;
  489.         for (i = 0; i < newblock.nelmts; ++i)
  490.             newkey += newblock.node.intnode.key[i];
  491.  
  492.         if (pkey->pageno == rootpage)
  493.         {
  494.             /* split node was root, add a new level to B-Tree */
  495.             rootsplit(tree, rootpage, pkey, newpage, oldkey, newkey);
  496.             newblock.parent = rootpage;
  497.             write_node(pkey->pageno, &pkey->page);
  498.             write_node(newpage, &newblock);
  499.         }
  500.  
  501.         else
  502.         /* recursively add ptr/key pair corresponding to new node into
  503.         ** the parent of the old node */
  504.         {
  505.             write_node(pkey->pageno, &pkey->page);
  506.             write_node(newpage, &newblock);
  507.             prt.pageno = pkey->page.parent;
  508.             parentkey(pkey->pageno, &prt);
  509.             prt.page.node.intnode.key[prt.offset] = oldkey;
  510.             insert_key(tree, rootpage, newpage, newkey, &prt);
  511.         }
  512.     }
  513. }
  514.  
  515. /*    Form a new root with two children since the old root was split.
  516. **
  517. **    Parameters :
  518. **        tree - BTree filename (I)
  519. **        oldroot - split root (I, O)
  520. **        rpageno - page number of new root's right child (I)
  521. **        rkey - key of new root's right child (I)
  522. */
  523.  
  524. rootsplit(tree, rootpage, oldroot, rpageno, lkey, rkey)
  525.  
  526. char *tree;
  527. long rootpage;
  528. register struct locator *oldroot;
  529. long rpageno, lkey, rkey;
  530. {
  531.     struct BTreeNode    newroot, temp;
  532.     long            i;
  533.  
  534.     /* get a new page for the former root */
  535.     oldroot->pageno = new_page(tree);
  536.  
  537.     newroot.depth = oldroot->page.depth;
  538.     newroot.prevtree = oldroot->page.prevtree;
  539.     newroot.nexttree = oldroot->page.nexttree;
  540.     bmove(&oldroot->page.prttree, &newroot.prttree, LIDSIZE);
  541.     newroot.nodetype = 'I';
  542.     newroot.nelmts = 2;
  543.     newroot.parent = oldroot->page.parent;
  544.     oldroot->page.parent = rootpage;
  545.     oldroot->page.depth = 0;
  546.     newroot.node.intnode.key[0] = lkey;
  547.     newroot.node.intnode.ptr[0] = oldroot->pageno;
  548.     newroot.node.intnode.key[1] = rkey;
  549.     newroot.node.intnode.ptr[1] = rpageno;
  550.  
  551.     write_node(rootpage, &newroot);
  552.  
  553.     if (oldroot->page.nodetype == 'I')
  554.         /* make sure the children of the oldroot have the correct parent */
  555.         for (i = 0; i < oldroot->page.nelmts; ++i)
  556.         {
  557.             get_node(oldroot->page.node.intnode.ptr[i], &temp);
  558.             temp.parent = oldroot->pageno;
  559.             write_node(oldroot->page.node.intnode.ptr[i], &temp);
  560.         }
  561. }
  562.